#include "BinarySortTree.h"
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0

BTNode *CreateTreeNode(ElementType element)
{
    BTNode *treenode=(BTNode*)malloc(sizeof(BTNode));
    if(treenode==NULL)
    {
        printf("tree node malloc error\n");
        return NULL;
    }
    treenode->data=element;
    treenode->left=NULL;
    treenode->right=NULL;
    treenode->parent=NULL;
    return treenode;
}
//初始化
int InitLBTree(LBTree *tree,ElementType element)
{
    tree->root=CreateTreeNode(element);//给根申请内存并初始化
    if(tree->root==NULL)
    {
        printf("InitLbtree error\n");
        return false;
    }
    else
        return true;
}
//数据插入
void Insert(BTNode *node,ElementType element)
{
    if(node->data==element)
        return;
    if(node==NULL)
    {
        return;
    }
    if(node->left==NULL&&element<node->data)//小于node->data插左边
    {
        node->left=CreateTreeNode(element);
        node->left->parent=node;//将创建的节点的父节点指向自己
        return;
    }
    if(node->right==NULL&&element>node->data)//大于node->data插右边
    {
        node->right=CreateTreeNode(element);
        node->right->parent=node;//将创建的节点的父节点指向自己
        return;
    }
    //没位置插入往下递归
    if(element<node->data)
    {
        Insert(node->left,element);
    }
    else if(element>node->data)
    {
        Insert(node->right,element);
    }
}

void InsertNode(LBTree *tree, ElementType element)
{
    Insert(tree->root,element);
}
//中序遍历
void MidPrint(BTNode *node)
{
    if(node!=NULL)
    {
        MidPrint(node->left);
        printf("%d ",node->data);
        MidPrint(node->right);
    } 
}
void MidTravel(LBTree *tree)
{
    MidPrint(tree->root);
    printf("\n");
}
//前序遍历
void PrevPrint(BTNode *node)
{
    if(node!=NULL)
    {
        printf("%d ",node->data);
        PrevPrint(node->left);
        PrevPrint(node->right);
    }
    
}
void PrevTravel(LBTree *tree)
{
    PrevPrint(tree->root);
    printf("\n");
}
//后序遍历
void PostPrint(BTNode *node)
{
    if(node!=NULL)
    {
        PostPrint(node->left);
        PostPrint(node->right);
        printf("%d ",node->data);
    } 
}
void PostTravel(LBTree *tree)
{
    PostPrint(tree->root);
    printf("\n");
}
//根据数据找节点
BTNode *SearchNode(BTNode *node,ElementType element)
{
    if(node==NULL)
    {
        return NULL;
    }
    if(node->data==element)//node->data==element直接返回该节点
    {
        return node;
    }
    else if(node->data<element)
    {
        return SearchNode(node->right,element);//node->data<element往左遍历
    }
    else if(node->data>element)
    {
        return SearchNode(node->left,element);//node->data>element往尤遍历
    }
}
BTNode *SearchElement(LBTree *tree, ElementType element)
{

    return SearchNode(tree->root,element);
}

//数据删除
void DeleteElement(LBTree *tree, ElementType element)
{
    BTNode *targetnode=SearchNode(tree->root,element);//记下要删除的节点
    if(targetnode==NULL)
    {
        return;
    }
    if(targetnode->left==NULL&&targetnode->right==NULL&&targetnode->parent==NULL)//如果为根节点，并且左右都为空
    {
        tree->root=NULL;
        free(targetnode);
        return;
    }
    else if(targetnode->left==NULL&&targetnode->right==NULL)//如果不是根节点，但是左右都为空
    {
        if(targetnode->parent->left==targetnode)//判断该节点是否为该节点的父节点的左节点
            targetnode->parent->left=NULL;
        else
            targetnode->parent->right=NULL;
        free(targetnode);
    }
    else if(targetnode->right==NULL)//如果右节点为空
    {
        targetnode->left->parent=targetnode->parent;
        if(targetnode->parent==NULL)//如果为根节点
            tree->root=targetnode->left;
        else if(targetnode->parent->left==targetnode)//如果该节点的父节点的左节点等于该节点 
            targetnode->parent->left=targetnode->left;
        else
            targetnode->parent->right=targetnode->left;   
        free(targetnode);
    }
    else if(targetnode->left==NULL) //如果该节点的左节点为空
    {
        targetnode->right->parent=targetnode->parent;
        if(targetnode->parent==NULL)//如果为根节点
            tree->root=targetnode->right;
        else if(targetnode->parent->right==targetnode)//如果该节点的父节点的右节点等于该节点
            targetnode->parent->right=targetnode->right;
        else
            targetnode->parent->left=targetnode->right;
        free(targetnode);
    }
    else if(targetnode->left!=NULL&&targetnode->right!=NULL)//如果该节点的左右节点都不为空
    {
        BTNode *minnode=targetnode->right;//记下该节点的右节点
        while(minnode->left!=NULL)//为空截至
        {
            minnode=minnode->left;//向左遍历
        }
        targetnode->data=minnode->data;
        if(minnode->parent!=targetnode)//如果minnode->parent!=targetnode
        {
            minnode->parent->left=minnode->right;//挂左边
        }
        else
        {
            targetnode->right=minnode->right;//挂右边
        }
        free(minnode);
    }
}

void FreeBTNode(BTNode *node)
{
    if(node==NULL)
        return;
    FreeBTNode(node->left);//左遍历
    FreeBTNode(node->right);//右遍历
    free(node);//释放自己
}
void FreeLBTree(LBTree *tree)
{
    FreeBTNode(tree->root);
    tree->root=NULL;
}
